package com.github.yangyishe.p300;

import java.util.*;

/**
 * 210. 课程表 II
 * https://leetcode.cn/problems/course-schedule-ii/description/?envType=study-plan-v2&envId=top-interview-150
 * todo 已做完,但效率较低,以后有时间看标准答案
 *
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
 *
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：[0,1]
 * 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 * 示例 2：
 *
 * 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
 * 输出：[0,2,1,3]
 * 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
 * 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
 * 示例 3：
 *
 * 输入：numCourses = 1, prerequisites = []
 * 输出：[0]
 *
 *
 * 提示：
 * 1 <= numCourses <= 2000
 * 0 <= prerequisites.length <= numCourses * (numCourses - 1)
 * prerequisites[i].length == 2
 * 0 <= ai, bi < numCourses
 * ai != bi
 * 所有[ai, bi] 互不相同
 */
public class Problem210 {
    public static void main(String[] args) {

    }

    /**
     * 思路:
     * 和p207相比, 思路比较相似, 只是多了一个记录环节
     * 换言之, 原来的p207应该是有更快的思路
     *
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        for(int i=0;i<numCourses;i++){
            fore2BackListMap.putIfAbsent(i,new ArrayList<>());
            back2CountMap.putIfAbsent(i,0);
        }
        for(int[] q:prerequisites){
            int back=q[0];
            int fore=q[1];

            fore2BackListMap.get(fore).add(back);
            back2CountMap.put(back,back2CountMap.get(back)+1);
        }
        for(int back:back2CountMap.keySet()){
            if(back2CountMap.get(back)==0){
                courseQueue.addLast(back);
                learnedSet.add(back);
            }
        }
        int[] resultArr=new int[numCourses];
        int index=0;
        while(!courseQueue.isEmpty()){
            Integer course = courseQueue.removeFirst();
            resultArr[index++]=course;
            chooseCourse(course);
        }


        return learnedSet.size()==numCourses?resultArr:new int[0];
    }

    // 前2后listMap
    private Map<Integer, List<Integer>> fore2BackListMap=new HashMap<>();

    // 后2countMap
    private Map<Integer,Integer> back2CountMap=new HashMap<>();

    // 已学课程
    private Set<Integer> learnedSet =new HashSet<>();
    private LinkedList<Integer> courseQueue=new LinkedList<>();

    private boolean chooseCourse(Integer course){
        boolean flag=false;
        List<Integer> backList=fore2BackListMap.get(course);
        if (backList!=null) {
            for (Integer back : backList) {
                back2CountMap.put(back,back2CountMap.get(back)-1);
                if(back2CountMap.get(back)==0){
                    learnedSet.add(back);
                    courseQueue.addLast(back);
                    flag=true;
                }
            }
        }
        return flag;
    }
}
